package nku.csc364;

//All sorting methods in this class...
//Raj Akula



public class Sort {
	
	//Generic Selection Sort
	//Take in an array of comparble objects!!!!
	public static void SelectionSort(Comparable [] x){
		for(int i = 0; i < x.length-1; i++){
			for(int j = i+1; j < x.length; j++){
				if(x[i].compareTo(x[j]) > 0 ){
					Comparable temp = x[i];
					x[i] = x[j];
					x[j] = temp;
					
				}
			}
		
		}
	}
	
	//Generic Quick Sort
	//Take in an array of comparble objects!!!!
	public static void quickSort(Comparable[] x){
		quickSort(x, 0, x.length - 1);
	}
	
	//Generic Quick Sort helper method
	public static void quickSort(Comparable[] x, int low, int high){ 
	        if (high <= low)
	        	return;
	        int j = partition(x, low, high);
	        quickSort(x, low, j-1);
	        quickSort(x, j+1, high);
	}
	
	
	private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = a[lo];
        while(true) { 

            // find item on lo to swap
            while (less(a[++i], v))
                if (i == hi) break;

            // find item on hi to swap
            while (less(v, a[--j]))
                if (j == lo) break;      // redundant since a[lo] acts as sentinel

            // check if pointers cross
            if (i >= j) break;

            exch(a, i, j);
        }

        // put v = a[j] into position
        exch(a, lo, j);

        // with a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
        return j;
    }
	
	// is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }
        
    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
	
	//Generic Merge Sort
	//Take in an array of comparable objects!!!!
	public static void mergeSort(Comparable [] a) {
        Comparable [] tmpArray = new Comparable[a.length];
        mergeSort(a, tmpArray, 0, a.length - 1);
    }
    
	// Merge Sort helper method
    private static void mergeSort(Comparable [] a, Comparable [] tmpArray, int left, int right ) {
        if(left < right) {
            int center = (left + right) / 2;
            mergeSort(a, tmpArray, left, center);
            mergeSort(a, tmpArray, center + 1, right);
            merge(a, tmpArray, left, center + 1, right);
        }
    }
    
    //Method to merge after dividing the elements
    private static void merge(Comparable [] a, Comparable [] tmpArray, int leftPos, int rightPos, int rightEnd ) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        
        // Main loop
        while((leftPos <= leftEnd) && (rightPos <= rightEnd) )
            if(a[leftPos].compareTo(a[rightPos]) <= 0 )
                tmpArray[tmpPos++] = a[leftPos++];
            else
                tmpArray[tmpPos++] = a[rightPos++];
        
        while(leftPos <= leftEnd)    // Copy rest of first half
            tmpArray[tmpPos++] = a[leftPos++];
        
        while(rightPos <= rightEnd)  // Copy rest of right half
            tmpArray[tmpPos++] = a[rightPos++];
        
        // Copy tmpArray back
        for(int i = 0; i < numElements; i++, rightEnd--)
            a[rightEnd] = tmpArray[rightEnd];
    }
	
}
